package com.tensai.study.java.basic.algorithm.recursion;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 整数划分问题
 */
@Slf4j
public class IntegerSplitTest {

	/**
	 * 把n分解为数个自然数的加和，且其中最大自然数不超过m
	 *
	 * @param n 要分解的自然数
	 * @param m 分解的最大自然数
	 * @return 可分解次数
	 */
	public int q(int n, int m) {
		if (n < 1 || m < 1) {
			log.error("q({},{}) = {}", n, m, 0);
			return 0;
		}
		if (n == 1 || m == 1) {
			log.warn("q({},{}) = {}", n, m, 1);
			return 1;
		}
		if (n < m) {
			log.warn("q({},{}) = q({},{})", n, m, n, n);
			return q(n, n);
		}
		if (n == m) {
			log.warn("q({},{}) = q({},{})+1", n, m, n, m - 1);
			return q(n, m - 1) + 1;
		}
		log.warn("q({},{}) = q({},{})+q({},{})", n, m, n, m - 1, n - m, m);
		return q(n, m - 1) + q(n - m, m);
	}

	@Test
	public void test() {
		log.info(q(6, 4) + "");
	}
}
